20周年だし幅優先社長探索してみた【競プロネタ】 #クラスメソッド20th

20周年だし社長に会いたい。でも私は地方オフィス所属（茶番部分）

本日2023年7月7日をもって弊社は20年目を迎えるようです。すごいですね。

私個人としてはクラスメソッドにちょうど1年ほど在籍しています。

時間さえあれば社長に聞いてみたい話、話したい雑談は山ほどあります。

• 私が趣味で競技プログラミング（以下競プロと省略）をしていること
• クラスメソッドに入ってからお世話になってきた方々のこと
• クラスメソッドの文化のこと

しかし、あいにく私は福岡オフィスの所属でありなかなか本社に行く機会がありません。

仮に東京に行けたとしても、社長も忙しい身であるため、いろいろな人づてに居場所を聞かないとなかなか会えないかもしれません。

そこで「社長を探しに行って競技プログラミングの話をする」ことは諦めて「競技プログラミングの問題中で社長を探してみる」ことにしました。

※ 無理やり20周年と趣味の競技プログラミングを結び付けようとした結果こうなりました。

先に結論

忙しい方のために、先に結論を申し上げると、私が以下のような実装で無事社長に会え、最短経路も判明しました！

是非社長に会う最短経路がわからない方は、同じように幅優先探索アルゴリズムなどを利用してみてください！

from collections import deque

# 入力の受け取り
N = int(input())
names = [input() for _ in range(N)]  # 頂点の名前を受け取る
M = int(input())  # 辺の数を受け取る
# グラフの生成
graphs = [[] for _ in range(N)]
for _ in range(M):
    # どの頂点同士が繋がっているか受け取る
    v1, v2 = map(int, input().split())
    # 辺で繋がっている頂点同士は互いに行き来ができるので双方向に繋げる
    graphs[v1].append(v2)
    graphs[v2].append(v1)

# 私の要素番号を取得（スタート地点）
start = names.index("私")
# 社長の要素番号を取得（ゴール地点）
goal = names.index("社長")
q = deque([start])
# 各頂点までの最短距離を管理する配列
dist_list = [-1] * N
dist_list[start] = 0
# 経路を復元するために、特定の頂点に辿り着く前にどの頂点を通ってきたかを記録する配列
prev_nodes = [-1] * N

while len(q) > 0:
    # 探索する頂点をキューから取り出す
    cur_node = q.popleft()
    # その頂点がゴール（社長）なら終了
    if cur_node == goal:
        print("やっと会えましたね！ここまでくるのに{}手必要でしたよ。".format(dist_list[cur_node]))
        break
    for next_node in graphs[cur_node]:
        # 距離が-1（初期値）ではないなら、すでに訪れている頂点なのでスキップ
        if dist_list[next_node] != -1:
            continue
        dist_list[next_node] = dist_list[cur_node] + 1
        prev_nodes[next_node] = cur_node
        q.append(next_node)
# 経路を復元する
route_list = []
cur_node = goal
while cur_node != start:
    route_list.append(cur_node)
    cur_node = prev_nodes[cur_node]
route_list.reverse()
print("ここまでの経路は")
for node in route_list:
    name = names[node]
    print(name)
print("です")

東京に行かなくても、プログラムの上でなら数十行程度で社長に会えるのは素晴らしいですね。

また、社長に会うコードを自分で実装したい方には入力値のサンプルも用意しています。

名前はFakerで作成したダミーデータとなります。

これでいつでも社長を探しにいけますね。

※ いつも参加している競技プログラミングのノリで処理を書いていますが、実業務では上記のような見にくいコードは使わないように気をつけます

免責事項

• 私は競技プログラミングを趣味としていますが、その道の第一人者ではなく、「非常に得意」というわけでもありません
• そのため説明や解法が誤っていたり、効率的ではないことが想定されます
• 会社の設立記念に乗じて1年間の間で覚えた典型的な技法（幅優先探索）を実装したかっただけです。申し訳ありません。

解決したい問題（上で実装したコードが解決すること）

やりたいこと

以下の図（グラフ）をご覧ください。

• これは社員との関係的なものを表したグラフとなります
• 丸い形となっているのが社員（人）を表現しています
• 直接線で繋がっている社員はお互いの場所をしっています
• 上の図の場合、私はAさんと相互に居場所をしっています
  • AさんはBさんと
  • BさんはCさんと・・・
  • という関係があります

このように何かと何かの関係をグラフと呼ばれる形で表現できます（友人関係とか、SNSのフォロー関係などもグラフで表現できます）。

上の図はシンプルに一直線につながっていますが、クラスメソッドも社員が多くなっているので実際は以下のグラフのように複雑なグラフになることが想定されます。

社員も何百人もいると、それぞれのネットワークも凄そうです。

今からちょっとかっこよく「社員」のことを頂点、「社員と社員の間の線」のことを辺と呼称します。

私は最短経路で社長に会いたいので、なんとか最短経路（最小限の頂点を辿る）で会える方法を探したいと思います。

そこで、課題解決のアプローチとして幅優先探索という手法を使ってみようと思います。

幅優先探索というのアルゴリズムは聞いたことがあるが、実装したことはないという方も多いのではないでしょうか。

実際に実装する必要はありませんが、以下の記事が考え方の理解にとても良いので、ぜひご覧ください。

入力値（頂点の情報、辺の情報）

さて、問題を解くにあたって以下のような情報が必要になります。

• 頂点（社員）の数
• どの頂点と頂点が辺でつながっているのか
• 辺の数

競技プログラミングにおいては、標準入力から入力値が渡されることが多いです。

今回も以下のような形式で入力が渡されます。

# 1行目で頂点の数が渡される
N
# ここからN行分頂点（社員）の名前が渡される
頂点の名前1
頂点の名前2
...
頂点の名前N
# 頂点の情報の後に辺の数が渡される
M（辺の数。ここから辺で繋がっている頂点の情報が出力される）
頂点情報1,1 頂点情報1,2 #スペース区切りで頂点の番号がM行分与えられる
...
頂点情報M,1 頂点情報M,2 #M行分情報が与えられる
# 例えば以下の入力値は社員(頂点)1と社員(頂点)3が辺でつながっていることを表す
# 1 3

分かりにくいですよね。

具体例でみてましょう。

• 頂点（社員）は4
• 辺の数は3

4
私
Aさん
Bさん
社長
3
0 1 #私とAさんの間に辺がある
1 2 #私とBさんの間に辺がある
2 3 #Bさんと社長の間に辺がある

グラフで表すと以下のような状況ですね。

入力値の制約

• 頂点の数Nは500で固定
• 辺の数Mは800で固定
• 「私」と「社長」という頂点は必ず与えられる
• 「私」と「社長」の頂点には必ず到着できる経路が存在することが保証されます
  • ※ せっかく探しに行って会えないのは寂しいですからね

実装してみる

ということで早速実装していこうと思います。

入力値の受け取りとグラフの作成

標準入力から、頂点の情報や辺の情報を受け取りながらグラフの情報を保持していきます。

# 入力の受け取り
N = int(input())
names = [input() for _ in range(N)]  # 頂点の名前を500個受け取る
M = int(input())  # 辺の数を受け取る（今回は800で固定）

まずは頂点の数（N）、頂点（社員）の名前、辺の数（M）を受け取っていきます。

Pythonだとinput()で標準出力から情報を受け取れます。

names = [input() for _ in range(N)]はカッコつけている感じがしますが、やっていることは以下と同じです。

names = []
for i in range(N):
    name = input()
    names.append(name)

次にグラフを作成するのですが、隣接リスト表現という形式でグラフを作ってみます。

もう一度以下のグラフを使ってみます。

この時以下のように二次元のリストでグラフを表現します。

[
    [1], #1番目（index:0）の人（私）が誰とつながっているか
    [0,2], #2番目(index:1)の人（Aさん）が誰とつながっているか
    [1,3], #3番目(index:2)の人（Bさん）が誰とつながっているか
    [2], #3番目(index:3)の人（社長）が誰とつながっているか
]

今回の場合Aさんと私との間に辺がある場合、相互に知っているという条件になっているので、以下のように表現されるわけですね。

[
    [1], #1はAさんのこと、私はAさんのことしか知らない
    [0,2] #0は私のこと、Aさんは私と2（Bさん）のことを知っている
]

ということで、グラフを作る部分を以下のように実装しています。

# グラフの生成
graphs = [[] for _ in range(N)] #2次元配列を作っている。
for _ in range(M):
    # どの頂点同士が繋がっているか受け取る
    # ちなみにvはvertexの略で英語で頂点という意味になるそうです
    v1, v2 = map(int, input().split())
    # 辺で繋がっている頂点同士は互いに行き来ができるので双方向に繋げる
    graphs[v1].append(v2)
    graphs[v2].append(v1)

私から社長への経路を探すための情報の格納庫を用意する

今回の目的は「私」から「社長」の最短の経路を求めることなので、色々と準備をしていきます。

from collections import deque #リストより効率良く情報を格納・取り出しできるデータ構造を用意

# 私の要素番号を取得（スタート地点を把握）
start = names.index("私")
# 社長の要素番号を取得（ゴール地点を把握）
goal = names.index("社長")
# キューというデータ構造を用意して効率的に情報を出し入れできるようにする
q = deque([start])
# 各頂点までの最短距離を管理する配列
dist_list = [-1] * N
dist_list[start] = 0
# 経路を復元するために、特定の頂点に辿り着く前にどの頂点を通ってきたかを記録する配列
prev_nodes = [-1] * N

今回も初見で見るとさっぱり分かりませんね。

startとgoalはなんとなくわかると思いますので、説明を割愛します。

q = deque([start])

こちらの部分に関しては、幅優先探索という探索法をするにあたって、効率的に情報を出し入れできるデータ構造を用意しています。

コンピュータサイエンスを学習した方や、基本情報技術者試験などの学習をされた方はピンと来られたかもしれません。

以下の記事がとっても分かりやすいのですが、要するにキューは「筒」のようなもので、先に入れたものが一番最初に出てくるようになっています。

次に、以下の部分を解説します。

# 各頂点までの最短距離を管理する配列
dist_list = [-1] * N
dist_list[start] = 0
# 経路を復元するために、特定の頂点に辿り着く前にどの頂点を通ってきたかを記録する配列
prev_nodes = [-1] * N

今回は社長に会うための最短経路を求めたいのですが、ついでに何手で行けるのかも調べてみたいと思います。

dist_listには私から各頂点に辿り着くまでの最短の手数、prev_nodesには「私から拡張点に辿り着いた時に、どの頂点から来たか」という情報をメモしています。

これも以下の図で考えてみます。

dist_list[0] #0番目つまり私から私までの最短距離
dist_list[1] #1番目つまり私からAさんまでの最短距離
dist_list[2] #2番目つまり私からBさんまでの最短距離
dist_list[3] #3番目つまり私から社長までの最短距離

という情報が格納されるということですね。

dist_list の各要素の初期値を-1としているのは、すでに辿り着いている頂点かどうか判別するという意味も兼ねています。

また、私から私までの距離は0に決まっているので以下の部分で0を格納しています。

dist_list[start] = 0

prev_listもdist_listと考え方は似ています。

prev_nodes[0] #私が0番目つまり私の頂点に辿り着く直前にどの頂点から来たか
prev_nodes[1] #私が1番目つまりAさんの頂点に辿り着く直前にどの頂点から来たか
prev_nodes[2] #私が2番目つまりBさんの頂点に辿り着く直前にどの頂点から来たか
prev_nodes[3] #私が2番目つまり社長の頂点に辿り着く直前にどの頂点から来たか

今回の例で言えば以下のようなデータが格納されることになります。

prev_nodes[0] #-1のまま
prev_nodes[1] #0 つまりAさんには私から到着した
prev_nodes[2] #1 つまりBさんにはAさんから到着した
prev_nodes[3] #2 つまり社長にはBさんから到着した

いよいよ社長を探すたびに出る

いよいよ以下のように社長を探して探索を始めていきます。

while len(q) > 0:
    # 次に探索する頂点をキューから取り出す
    cur_node = q.popleft()
    # 次に探索する頂点がゴールなら終了
    if cur_node == goal:
        print("やっと会えましたね！ここまでくるのに{}手必要でしたよ！".format(dist_list[cur_node]))
        break
    for next_node in graphs[cur_node]:
        # 距離が-1（初期値）ではないなら、すでに訪れている頂点なのでスキップ
        if dist_list[next_node] != -1:
            continue
        dist_list[next_node] = dist_list[cur_node] + 1
        prev_nodes[next_node] = cur_node
        q.append(next_node)

まず幅優先探索なのですが、私から近い頂点から順に探していく探し方になります。

以下のグラフで考えてみます。

• まず私からみてAさん、Bさんとつながっていることがわかります
• 以下のようにキューに情報を入れます。

※ わかりやすくAさんBさんと人の名前を入れていますが、実際は頂点のindexが入ってきます

q = [Aさん,Bさん]

• 次に先頭のAさんの情報を取り出します

cur_node = q.pop() #先頭から取り出す
# q = [Bさん]となる

• Aさんはまだ未訪問なので、AさんがDさんとつながっているっぽいのでDさんの情報をキューに入れます

q.append(Dさん)
# q = [Bさん,Dさん]

• 次にキューの先頭からBさんを取り出す・・・

とこのように、私に近い頂点から順に探索していくようなイメージです。

というのを実装したのが以下の実装となります（再掲）

# キューに次の頂点の情報がある間は繰り返す
while len(q) > 0:
    # 次に探索する頂点をキューの先頭から取り出す
    cur_node = q.popleft()
    # 次に探索する頂点がゴールなら終了
    if cur_node == goal:
        print("やっと会えましたね！ここまでくるのに{}手必要でしたよ！".format(dist_list[cur_node]))
        break
    # 探索する頂点がどこの頂点とつながっているか調べる
    for next_node in graphs[cur_node]:
        # 距離が-1（初期値）ではないなら、すでに訪れている頂点なのでスキップ
        if dist_list[next_node] != -1:
            continue
        # 私からの最短距離を格納する
        dist_list[next_node] = dist_list[cur_node] + 1
        # この頂点に辿り着く直前の頂点の情報を格納する
        prev_nodes[next_node] = cur_node
        q.append(next_node)

情報量こそ多いものの、やっていることは筒から情報を取りだしたり、入れたりしていると考えれば実はそんなに難しくなかったりします。

最後に経路を復元する（最短経路を表示する）

ということで、最後に最短経路を復元してみたいと思います。

# 経路を復元する
route_list = []
# ゴール（社長）から遡る
cur_node = goal
# スタート地点（私）にいたるまで続ける
while cur_node != start:
    route_list.append(cur_node)
    # 記録していた「前に到達していた頂点」を遡る
    cur_node = prev_nodes[cur_node]
# ゴールから遡っていたのでひっくり返す
route_list.reverse()
print("ここまでの経路は")
for node in route_list:
    # 頂点のindexではなく名前に変換して出力する
    name = names[node]
    print(name)
print("です")

今まで記録していた経路を遡って、最短経路を復元するということをしています。

サンプルファイルで確かめてみる

ということで、ここまでのコードの全貌は以下のようになります。

from collections import deque

# 入力の受け取り
N = int(input())
names = [input() for _ in range(N)]  # 頂点の名前を500個受け取る
M = int(input())  # 辺の数を受け取る（今回は800で固定）
# グラフの生成
graphs = [[] for _ in range(N)]
for _ in range(M):
    # どの頂点同士が繋がっているか受け取る
    v1, v2 = map(int, input().split())
    # 辺で繋がっている頂点同士は互いに行き来ができるので双方向に繋げる
    graphs[v1].append(v2)
    graphs[v2].append(v1)

# 私の要素番号を取得（スタート地点）
start = names.index("私")
# 社長の要素番号を取得（ゴール地点）
goal = names.index("社長")
q = deque([start])
# 各頂点までの最短距離を管理する配列
dist_list = [-1] * N
dist_list[start] = 0
# 経路を復元するために、特定の頂点に辿り着く前にどの頂点を通ってきたかを記録する配列
prev_nodes = [-1] * N

while len(q) > 0:
    # 次に探索する頂点をキューから取り出す
    cur_node = q.popleft()
    # 次に探索する頂点がゴールなら終了
    if cur_node == goal:
        print("やっと会えましたね！ここまでくるのに{}手必要でしたよ。".format(dist_list[cur_node]))
        break
    for next_node in graphs[cur_node]:
        # 距離が-1（初期値）ではないなら、すでに訪れている頂点なのでスキップ
        if dist_list[next_node] != -1:
            continue
        dist_list[next_node] = dist_list[cur_node] + 1
        prev_nodes[next_node] = cur_node
        q.append(next_node)
# 経路を復元する
route_list = []
cur_node = goal
while cur_node != start:
    route_list.append(cur_node)
    cur_node = prev_nodes[cur_node]
route_list.reverse()
print("ここまでの経路は")
for node in route_list:
    name = names[node]
    print(name)
print("です")

うーん。これは実務だとめっちゃダメなコードとなってしまいましたね。

競技プログラミングのコンテストには 早く 正確かつ効率的な コードを書くことを目的にしているので、今回も似たようなノリで実装してしまいました。（変数名はだいぶ気をつかっている方ですが）

とりあえず、解答を実装する時間の5倍くらい時間のかかったサンプルの入力値を用意しているのでさっそく実行してみようと思います。

※ こちらの氏名は全てFakerで作成した偽名です

python3 tansaku.py

とすると以下のように最短経路の頂点の名前が表示されます。

やっと会えましたね！ここまでくるのに9手必要でしたよ。
ここまでの経路は
20
周
年
お
め
で
と
う
社長
です

（ニッコリ）

最後に

ここまでお付き合いして下さった方は、本当にありがとうございます。

今回は20周年に乗じて、私の趣味が多分に入った記事となってしまい申し訳ありません。

一つの会社を20年も存続させるだけでも大変な中、クラスメソッドでは様々な新しい取り組みにもチャレンジしています。

ぜひ弊社にご興味のある方は私でも良いのでお声がけください。

以上、今泉でした。本当に最後までお付き合いいただき、ありがとうございました。